package org.raymond.iworks.study.basic.structure.stack;

/**
 * @author raymond
 * @version V1.0
 * @Description:
 * test1,test2实现的是中缀表达式计算器
 * 前缀表达式:
 * 1)前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前
 * 2)举例说明: (3+4)*5-6,对应的前缀表达式是: -X+3456
 * 前缀表达式的程序处理逻辑:
 * 从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做出相应的计算
 * (栈顶元素和次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果
 * 例如: (3+4)*5-6,对应的前缀表达式是: -X+3456,针对前缀表达式求值步骤如下:
 * 1)从右至左扫描,将6,5,4,3压入堆栈
 * 2)遇到+运算符,因此弹出3和4(3为栈顶元素,4为次顶元素),计算出3+4的值,得7,再将7入栈
 * 3)接下来是x运算符,因此弹出7和5,计算出7x5=35,将35入栈
 * 4)最后是-运算符,计算出35-6的值,即29,由此得出最终结果
 * 中缀表达式:
 * 1)就是常见的运算表达式
 * 2)对计算机来说却不好操作(需要判断括号的优先级,比较复杂),因此,在计算表达式时,常常会将中缀表达式转成其他表达式来操作
 * (一般是转成后缀)
 * 后缀表达式:
 * 1)后缀表达式又称逆波兰表达式,与前缀表达式相似,只是运算符位于操作数之后
 * 2)例如:(3+4)*5-6,对应的后缀表达式:34+5x6-
 * 3)其他例子:
 * 中缀       后缀
 * a+b        ab+
 * a+(b-c)    abc-+
 * a+(b-c)xd  abc-dx+
 * a+dx(b-c)  adbc-x+
 * a=1+3      a13+=
 * 后缀表达式的程序处理逻辑:
 * 从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做出相应的计算
 * (栈顶元素和次顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果
 * 例如: (3+4)*5-6,对应的后缀表达式是: 34+5x6-,针对后缀表达式求值步骤如下:
 * 1)从左至右扫描,将3和4压入堆栈
 * 2)遇到+运算符,因此弹出4和3(4为栈顶元素,3为次顶元素),计算出3+4的值,得7,再将7入栈
 * 3)将5入栈
 * 4)接下来是x运算符,因此弹出5和7,计算出5x7=35,将35入栈
 * 5)将6入栈
 * 6)最后是-运算符,计算出35-6的值,即29,由此得出最终结果
 */
public class Calculator {
    public static void main(String[] args) {
        String expr = "700+2*6-4/2";
        // 中缀表达式综合计算器
        test2(expr);
    }

    /**
     * 存在的问题:对多位数识别有问题.因为遇到数字就直接压入数栈,比如70,压入栈就是7,0,取出就是07.而且是视为两个数
     * 解决方案:处理数字时,需要一次拿出完整的数字,直到遇到符号
     */
    public static void test1(String expr){
        ArrayStack2 numStack = new ArrayStack2(10);
        ArrayStack2 operStack = new ArrayStack2(10);
        // 扫描表达式
        for(int i=0; i<expr.length(); i++){
            char c = expr.charAt(i);
            if(ArrayStack2.isOper(c)){
                int p1 = ArrayStack2.priority(c);
                try{
                    int p2 = ArrayStack2.priority(operStack.peek());
                    // 新扫描的操作符的优先级小于栈中的优先级,需要先计算中间值
                    if(p1<p2) {
                        int res=cal(numStack, operStack);
                        numStack.push(res);
                    }
                }catch (Exception e){
                    System.err.println(e.getMessage());
                    // 如果operStack为空,异常抛到这里,不做其他处理直接入栈
                }
                operStack.push(c);
            }else{
                numStack.push(c-48);
            }
        }
        // 计算
        int res = 0;
        while(!operStack.isEmpty()){
            res = cal(numStack, operStack);
            numStack.push(res);
        }

        System.out.printf("计算结果:%d\n", res);
    }

    public static void test2(String expr){
        ArrayStack2 numStack = new ArrayStack2(10);
        ArrayStack2 operStack = new ArrayStack2(10);
        String appendNumStr="";
        // 扫描表达式
        for(int i=0; i<expr.length(); i++){
            char c = expr.charAt(i);
            if(ArrayStack2.isOper(c)){
                int p1 = ArrayStack2.priority(c);
                try{
                    int p2 = ArrayStack2.priority(operStack.peek());
                    // 新扫描的操作符的优先级小于栈中的优先级,需要先计算中间值
                    if(p1<p2) {
                        int res=cal(numStack, operStack);
                        numStack.push(res);
                    }
                }catch (Exception e){
                    System.err.println(e.getMessage());
                    // 如果operStack为空,异常抛到这里,不做其他处理直接入栈
                }
                operStack.push(c);
            }else{
                // 累计表达式中的数字为一个完整的数
                appendNumStr += c;
                // 如果c已经是最后一位,就直接入栈
                if(i==expr.length()-1){
                    numStack.push(Integer.parseInt(appendNumStr));
                    appendNumStr="";
                // 累计数字,直到遇到操作符,累计的数字才能压入数栈
                }else if(ArrayStack2.isOper(expr.charAt(i+1))){
                    numStack.push(Integer.parseInt(appendNumStr));
                    // 用完后清空
                    appendNumStr="";
                }
            }
        }
        // 计算
        int res = 0;
        while(!operStack.isEmpty()){
            res = cal(numStack, operStack);
            numStack.push(res);
        }

        System.out.printf("计算结果:%d\n", res);
    }

    public static int cal(ArrayStack2 numStack, ArrayStack2 operStack){
        int num1=numStack.pop();
        int num2=numStack.pop();
        int oper=operStack.pop();
        return ArrayStack2.cal(num1,num2,oper);
    }
}
